﻿using Microsoft.Xna.Framework;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace XNA_TD
{
    public class Node : IComparable<Node>
    {
        public Vector2 position;
        public Node next;
        public double travelDistance;

        public Node(Vector2 pos)
        {
            position = pos;
            travelDistance = 0;
            next = null;
        }

        public void addNext(Node ne)
        {
            double newDistance = (position - ne.position).Length() + ne.travelDistance;
            if (next == null || travelDistance > newDistance)
            {
                travelDistance = newDistance;
                next = ne;
            }
        }

        public override string ToString()
        {
            return position.ToString();
        }

        public int CompareTo(Node other)
        {
            return (int)((travelDistance - other.travelDistance) * 100);
        }
    }

    public class Pfad : IRunable
    {
        Dictionary<Point, Node> nodes = null;
        static readonly int[] anleigende = new int[2] { -1, 1 };

        public Pfad()
            : base(Priority.Logic)
        {
            nodes = new Dictionary<Point, Node>();
            Recalculate();
        }

        public void Recalculate()
        {
            nodes.Clear();
            // erstmal alle erstellen die begehbar sind
            foreach (var point in map.bebaubar)
            {
                if (map.istBefahrbahr(point.Key))
                {
                    nodes.Add(new Point((int)point.Key.X, (int)point.Key.Y), new Node(point.Key));
                }
            }

            List<Point> visited = new List<Point>();
            List<Node> toTest = new List<Node>();
            toTest.Add(nodes[new Point((int)map.end.X, (int)map.end.Y)]);

            while (toTest.Count() > 0)
            {
                toTest.Sort();
                var node = toTest[0];
                toTest.RemoveAt(0);
                Point startPoint = getPoint(node.position);
                Point point;
                visited.Add(startPoint);

                foreach (var changeX in anleigende)
                {
                    startPoint = getPoint(node.position);
                    int maxX;

                    point = getPoint(startPoint);
                    point.X += changeX;
                    while (nodes.ContainsKey(point))
                    {
                        if (!visited.Contains(point))
                        {
                            nodes[point].addNext(node);
                            if (!toTest.Contains(nodes[point]))
                            {
                                toTest.Add(nodes[point]);
                            }
                        }
                        point.X += changeX;
                    }
                    maxX = Math.Abs(point.X);

                    foreach (var changeY in anleigende)
                    {
                        int currMaxX = maxX;
                        point = getPoint(startPoint);

                        while (nodes.ContainsKey(point))
                        {
                            point.Y += changeY;
                            while (nodes.ContainsKey(point) && Math.Abs(point.X) < currMaxX)
                            {
                                if (!visited.Contains(point))
                                {
                                    nodes[point].addNext(node);
                                    if (!toTest.Contains(nodes[point]))
                                    {
                                        toTest.Add(nodes[point]);
                                    }
                                }
                                point.X += changeX;
                            }
                            currMaxX = Math.Min(currMaxX, Math.Abs(point.X));
                            point.X = startPoint.X;
                        }
                    }
                }
            }
        }

        public Point getPoint(Vector2 pos)
        {
            int X = (int)Math.Round(pos.X);
            int Y = (int)Math.Round(pos.Y);
            return new Point(X, Y);
        }

        public Point getPoint(Point pos)
        {
            return new Point(pos.X, pos.Y);
        }

        public Vector2 getNext(Vector3 pos)
        {
            int X = (int)Math.Round(pos.X);
            int Y = (int)Math.Round(pos.Z);

            return nodes[new Point(X, Y)].next.position;
        }

        public Vector2 getNext(Vector2 pos)
        {
            int X = (int)Math.Round(pos.X);
            int Y = (int)Math.Round(pos.Y);

            return nodes[new Point(X, Y)].next.position;
        }

        public double getTravelDistance(Vector2 pos)
        {
            int X = (int)Math.Round(pos.X);
            int Y = (int)Math.Round(pos.Y);

            return nodes[new Point(X, Y)].travelDistance;
        }

        public bool has(Vector2 pos)
        {
            int X = (int)Math.Round(pos.X);
            int Y = (int)Math.Round(pos.Y);

            if (!nodes.ContainsKey(new Point(X, Y)))
                return false;
            return true;
        }

        public bool has(Vector3 pos)
        {
            int X = (int)Math.Round(pos.X);
            int Y = (int)Math.Round(pos.Z);

            if (!nodes.ContainsKey(new Point(X, Y)))
                return false;
            return true;
        }

        public bool hasNext(Vector2 pos)
        {
            int X = (int)Math.Round(pos.X);
            int Y = (int)Math.Round(pos.Y);

            if (!nodes.ContainsKey(new Point(X, Y)))
                return false;

            return nodes[new Point(X, Y)].next != null;
        }

        public bool hasNext(Vector3 pos)
        {
            int X = (int)Math.Round(pos.X);
            int Y = (int)Math.Round(pos.Z);

            if (!nodes.ContainsKey(new Point(X, Y)))
                return false;

            return nodes[new Point(X, Y)].next != null;
        }

        public override void Load()
        {
        }

        public override void UnLoad()
        {
        }
    }
}
